#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

string getString(const string &dst, const string &src, int i, int j, const vector<vector<int> > &dp)
{
    string ans;
    if (i < 1 || j < 1) return ans;

    if (dst[i-1] == src[j-1]) {
        ans = getString(dst, src, i-1, j-1, dp) + dst[i-1];
    } else {
        if (dp[i][j-1] > dp[i-1][j]) 
            ans = getString(dst, src, i, j-1, dp);
        else
            ans = getString(dst, src, i-1, j, dp);
    }
    return ans;
}

string longestCommonSequence(const string &src, const string &dst)
{
    int srcLen = src.size();
    int dstLen = dst.size();
    vector<vector<int> > dp(dstLen+1, vector<int>(srcLen+1, 0));

    for (int i = 1; i <= dstLen; i++) {
        for (int j = 1; j <= srcLen; j++) {
            if (dst[i-1] == src[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }   
    string ans = getString(dst, src, dstLen, srcLen, dp);
    return ans;
}

int main(int argc, char **argv)
{
    string src, dst, result;
    
    cout << "------------Test 1----------------" << endl;
    src = "abcdefghijklm";
    dst = "cfil";
    result = longestCommonSequence(src, dst);
    cout << src << "  and " << dst << endl;
    cout << "Result: " << result << endl;

    cout << "------------Test 2----------------" << endl;
    src = "abcdefghijklm";
    dst = "cf7878i78979l";
    result = longestCommonSequence(src, dst);
    cout << src << "  and " << dst << endl;
    cout << "Result: " << result << endl;


    cout << "------------Test 3----------------" << endl;
    src = "abcdefghijklm";
    dst = "";
    result = longestCommonSequence(src, dst);
    cout << src << "  and " << dst << endl;
    cout << "Result: " << result << endl;

    cout << "------------Test 4----------------" << endl;
    src = "abcdefghijklm";
    dst = "isdfjklcfil";
    result = longestCommonSequence(src, dst);
    cout << src << "  and " << dst << endl;
    cout << "Result: " << result << endl;
}
